package leetcode.other;


import java.util.LinkedList;

/**
 * @author cyt
 * @create 2020-08-12 13:46
 */
public class T0405 {
    static LinkedList<Integer> list = new LinkedList<Integer>();
    static TreeNode pre = null;

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node3 = new TreeNode(1);
        node.right = node3;
        boolean bst = isValidBST(node, list);
        System.out.println(bst);
        list.forEach(System.out::println);
    }

    public static boolean isValidBST(TreeNode root, LinkedList<Integer> list) {
        if (root == null) {
            return true;
        }
        dfs2(root);
        dfs(root, T0405.list);
        Integer first = T0405.list.getFirst();

        for (int i = 1; i < T0405.list.size(); i++) {
            if (first < T0405.list.get(i)) {
                return false;
            }
            first = T0405.list.get(i);
        }
        return true;
    }

    static boolean dfs2(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!dfs2(root.left)) {
            return false;
        }
        if (pre != null && root.val <= pre.val) {
            return false;
        }
        pre = root;
        if (!dfs2(root.right)) {
            return false;
        }
        return true;
    }

    public static void dfs(TreeNode root, LinkedList<Integer> list) {
        if (root.right != null) {
            dfs(root.right, list);
        }
        list.add(root.val);
        if (root.left != null) {
            dfs(root.left, list);
        }
    }
}
